//
// Created by francklinson on 2021/10/21 AT 9:47.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        digits.back() += 1;
        for (int i = digits.size() - 1; i > 0; --i) {
            if (digits[i] == 10) {
                digits[i] = 0;
                digits[i - 1] += 1;
            }
        }
        if (digits[0] == 10) {
            digits[0] = 0;
            digits.insert(digits.begin(), 1);
        }
        return digits;
    }
};

class Solution2 { // 题解
public:
    vector<int> plusOne(vector<int> &digits) {
        int n = (int)digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) { // 从后往前 第一位不为9的
                ++digits[i];   // +1
                for (int j = i + 1; j < n; ++j) { // 后面的9全部变为0
                    digits[j] = 0;
                }
                return digits;
            }
        }
        // 能走到这一步 说明 digits 中所有的元素均为 9 返回一个新的数组就行
        vector<int> ans(n + 1);
        ans[0] = 1;
        return ans;
    }
};


int main() {
    vector<int> digits{9, 9, 9};
    Solution solution;
    vector<int> ans = solution.plusOne(digits);
    for (auto &x: ans) {
        cout << x << endl;
    }
    return 0;
}

